import java.io.File;
import java.io.PrintWriter;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;


public class Planificacion2 {
	
	public static double TAMANIO_CELDA = 300;
	
	private Celda[][] celdas;
	
	private Point inicial;
	
	private Point fin;

	private ArrayList<Celda> esquinas;
	
	private ArrayList<Celda> lista;
	
	private char orientacionInicial;
	
	private char orientacionFinal;
	
	public void loadMap(File file)throws Exception{
		Scanner scan = new Scanner(file);
		scan.next();
		int px = scan.nextInt();
		int py = scan.nextInt();
		scan.nextInt();
		inicial = new Point(px,py);
		scan.next();
		px = scan.nextInt();
		py = scan.nextInt();
		scan.nextInt();
		fin = new Point(px,py);
		int filas = scan.nextInt();
		int cols = scan.nextInt();
		System.out.println(filas+"-"+cols);
		celdas = new Celda[filas][cols];
		int fi = 0,ci = 0,ff=0,cf=0;
		for (int i = 0; i < filas; i++) {
			for (int j = 0; j < cols; j++) {
				String s = scan.next();
				int p;
				char o = '-';
				if(s.equals("oo")){
					p = Celda.PARED;
				}else if(s.equals("..")){
					p = Celda.VACIA;
				}else if(s.startsWith("I")){
					p = Celda.INICIALA;
					o = s.charAt(1);
					orientacionInicial = o;
					ci=j;
					fi=i;
				}else{
					p = Celda.FINALA;
					o = s.charAt(1);
					orientacionFinal = o;
					cf=j;
					ff=i;	
				}
				celdas[i][j] = new Celda(p,o,i,j);
			}
		}
		
		generateMatrix(ff,cf);
		
		
		findPath(fi,ci);		
		
		String name = file.getAbsolutePath().substring(0, file.getAbsolutePath().length()-4)+"-camino.txt";
		File destiny = new File(name);
		printResults(destiny);
		
	}
	
	public void findPoints(String fileName)throws Exception{
		PrintWriter pw = new PrintWriter(new File(fileName));
		int dVisita = 100;
		int dMin = 90;
		pw.println(dVisita +" "+ dMin);
		//pw.println(inicial.getPosX() +" "+ inicial.getPosY());
		//pw.println(fin.getPosX() +" "+ fin.getPosY()+ " 90");
		pw.println(esquinas.size());
		for (Celda esquina : esquinas) {
			int fila = esquina.getFila();
			int columna = esquina.getColumna();
			double x = ((columna-1)*TAMANIO_CELDA + TAMANIO_CELDA/2 - inicial.getPosX());
			double y = ((celdas.length-fila-2)*TAMANIO_CELDA + TAMANIO_CELDA/2-inicial.getPosY());
			//referenciar las coordenadas de acuerdo a la orientacion inicial del robot
			if(orientacionInicial == 'N'){
				double tmp = x;
				x=y;
				y=-tmp;
			}else if(orientacionInicial == 'S'){
				double tmp = x;
				x=-y;
				y=tmp;
			}else if(orientacionInicial == 'E'){
				x = -x;
				y= -y;
			}
			pw.println( x+ " "+y);
		}
		pw.println("90");
		pw.close();
		
		
	}
	
	private void findPath(int fi,int ci){
		lista = new ArrayList();
		Celda c1 = celdas[fi][ci];
		lista.add(c1);
		esquinas = new ArrayList<Celda>();
		char lastDir = orientacionInicial;
		System.out.println("inicial:"+fi+","+ci);
		int[] mod = new int[4];
		if(lastDir=='N'){
			mod[0]=1;
		}else if(lastDir=='S'){
			mod[1]=1;
		}else if(lastDir=='E'){
			mod[2]=1;
		}else{
			mod[3]=1;
		}
		while(c1.getCosto()>=1){
			char actualDir='L';
			Celda ca = c1;
			Celda cn =celdas[c1.getFila()-1][c1.getColumna()]; 
			Celda cs =celdas[c1.getFila()+1][c1.getColumna()]; 
			Celda ce =celdas[c1.getFila()][c1.getColumna()+1];
			Celda cw =celdas[c1.getFila()][c1.getColumna()-1];
			System.out.println(Arrays.toString(mod));
			if(cn.getCosto()< c1.getCosto()+mod[0] && cn.getCosto()>=0){
				c1 = cn;
				actualDir='N';
			}
			if(ce.getCosto()< c1.getCosto()+mod[2] && ce.getCosto()>=0){
				c1 = ce;
				actualDir='E';
			}
			if(cs.getCosto()< c1.getCosto()+mod[1] && cs.getCosto()>=0){
				c1 = cs;
				actualDir='S';
			}
			if(cw.getCosto()< c1.getCosto()+mod[3] && cw.getCosto()>=0){
				c1 = cw;
				actualDir='W';

			}
			mod= new int[4];
			if(lastDir != actualDir){
				esquinas.add(ca);
				lastDir=actualDir;
				System.out.println("added");
			}
			lista.add(c1);
		}
		esquinas.add(c1);
	}
	
	private void generateMatrix(int ff, int cf){
		celdas[ff][cf].setCosto(0);
		Stack<Celda> ss = new Stack<Celda>();
		ss.add(celdas[ff][cf]);
		while(!ss.isEmpty()){
			Celda c = ss.pop();
			if(c.getEstado()== Celda.PARED){
				ss.remove(c);
				continue;
			}
			int n=2,w=2,e=2,s=2;
			
			if(c.getOrientacion()=='N'){
				n--;
			}else if(c.getOrientacion()=='W'){
				w--;
			}else if(c.getOrientacion()=='E'){
				e--;
			}else{
				s--;
			}
			
			Celda cn =celdas[c.getFila()+1][c.getColumna()]; 
			Celda cs =celdas[c.getFila()-1][c.getColumna()]; 
			Celda ce =celdas[c.getFila()][c.getColumna()-1]; 
			Celda cw =celdas[c.getFila()][c.getColumna()+1];
			
			if(cn.getEstado()*cs.getEstado()*ce.getEstado()*cw.getEstado()==0){
				c.setCosto(c.getCosto()+0.01);
			}
			
			if(cn.getEstado()!=Celda.PARED && (cn.getCosto()==-1 || cn.getCosto() > c.getCosto()+n)){
				cn.setCosto(c.getCosto()+n);
				cn.setOrientacion('N');
				ss.push(cn);
			}
			
			if(cs.getEstado()!=Celda.PARED && (cs.getCosto()==-1 || cs.getCosto() > c.getCosto()+s)){
				cs.setCosto(c.getCosto()+s);
				cs.setOrientacion('S');
				ss.push(cs);
			}
			
			if(ce.getEstado()!=Celda.PARED && (ce.getCosto()==-1 || ce.getCosto() > c.getCosto()+e)){
				ce.setCosto(c.getCosto()+e);
				ce.setOrientacion('E');
				ss.push(ce);
			}
			
			if(cw.getEstado()!=Celda.PARED && (cw.getCosto()==-1 || cw.getCosto() > c.getCosto()+w)){
				cw.setCosto(c.getCosto()+w);
				cw.setOrientacion('W');
				ss.push(cw);
			}
			
			ss.remove(c);
			
		}
	}
	
	public void printResults(File destiny) throws Exception{
		NumberFormat nf = NumberFormat.getInstance();
		nf.setMaximumFractionDigits(0);
		nf.setMinimumFractionDigits(0);
		nf.setMaximumIntegerDigits(2);
		nf.setMinimumIntegerDigits(2);
		
		for (int i = 0; i < celdas.length; i++) {
			for (int j = 0; j < celdas[0].length; j++) {
				if(celdas[i][j].getEstado()==Celda.PARED){
					System.out.print(" oo");
				}else{
					System.out.print(" "+nf.format(celdas[i][j].getCosto()));
				}
			}
			System.out.println();
		}
		
		
		
		PrintWriter pw = new PrintWriter(destiny);
		pw.println("QI "+ inicial.getPosX()+" "+inicial.getPosY());
		pw.println("QF "+ fin.getPosX()+" "+fin.getPosY());
		pw.println(celdas.length+" "+celdas[0].length);
		pw.println();
		pw.println("----------Costo movimiento----------");
		pw.println();
		for (int i = 0; i < celdas.length; i++) {
			String s = "";
			for (int j = 0; j < celdas[0].length; j++) {
				if(celdas[i][j].getEstado()==Celda.PARED){
					s+="oo ";
				}else{
					int l = -1;
					for (int j2 = 0; j2 < lista.size(); j2++) {
						if(lista.get(j2).getFila()==i && lista.get(j2).getColumna()==j){
							l=j2;
						}
					}
					if(l!=-1){
						s+=nf.format(lista.size()-l-1)+" ";
					}else{
						s+="-- ";
					}
				}
			}
			pw.println(s);
		}
		
		pw.close();
	}
	
	public static void main(String[] args) {
		try{
			Planificacion2 p = new Planificacion2();
			//p.loadMap(new File("problema2-mundo1-7x17.txt"));
			//p.findPoints("problema2-mundo1-7x17-puntos.txt");
			p.loadMap(new File("problema2-mundo2-7x17.txt"));
			p.findPoints("problema2-mundo2-7x17-puntos.txt");
			//p.loadMap(new File("problema2-mundo3-7x17.txt"));
			//p.findPoints("problema2-mundo3-7x17-puntos.txt");
			//p.loadMap(new File("problema2-mundo4-7x17.txt"));
			//p.findPoints("problema2-mundo4-7x17-puntos.txt");
			//p.loadMap(new File("problema2-mundo5-7x17.txt"));
			//p.findPoints("problema2-mundo5-7x17-puntos.txt");
		}catch (Exception e) {
			e.printStackTrace();
		}
	}
}
